//
// Created by Administrator on 2022/1/6.
//

#ifndef CPP_LEARNING_RB_TREE_H
#define CPP_LEARNING_RB_TREE_H

#include "BST.hpp"
#define IsBlack(p) (!(p) || (p)->color == RB_BLACK)
#define IsRed(x) (!IsBlack(x))
/**
 * 需要更新的情况
 * 1 左右孩子的黑高度不相等
 * 2 本身作为红节点，黑高度不与子节点相等
 * 3 本身作为黑节点，黑高度不等于子节点黑高度 + 1
 */
// 左右
#define BlackHeightUpdated(x) ( \
 (stature((x).lc) == stature((x).rc)) && \
 ((x).height == (IsRed(&x) ? stature((x).lc) : stature((x).lc) +1) \
 ))
template <typename T>
class RBTree: public BST<T>{
protected:
    void rightRotate(BinNodePosi(T) p);
    void leftRotate(BinNodePosi(T) p);
    void solveDoubleRed(BinNodePosi(T) node);  // 解决插入是的双红问题
    void solveDoubleBlack(BinNodePosi(T) r);
    int updateHeight(BinNodePosi(T) x);     // 更新节点的高度

public:
    virtual BinNodePosi(T) insert(const T& e);    // 插入
    virtual bool remove(const T&e);           // 删除
};

/**
 * 红节点是没有黑高度的
 * @tparam T
 * @param x
 * @return
 */
template <typename T>
int RBTree<T>::updateHeight(BinNodePosi(T) x){
    x->height = stature(x->lc) > stature(x->rc) ? stature(x->lc) : stature(x->rc);
    return IsBlack(x) ? x->height ++ : x->height;
}
template <typename T>
void RBTree<T>::solveDoubleBlack(BinNodePosi(T) r){
    BinNodePosi(T) p = r ? r->parent : this->_hot ;
    if(!p) return;                                       // p不存在就停止
    BinNodePosi(T) s = (r==p->lc) ? p->rc : p->lc;

    if(IsBlack(s)){
        BinNodePosi(T) t = NULL;
        if(IsRed(s->rc)) t = s->rc;
        if(IsRed(s->lc)) t = s->lc;

        if(t){   // 黑s有红色孩子 BB-1
            RBColor oldColor = p->color;
            BinNodePosi(T) b = FromParentTo(*p) = this->rotateAt(t);
            if(HasLChild(*b)) {
                b->lc->color = RB_BLACK;
                updateHeight(b->lc);
            }
            if(HasRChild(*b)) {
                b->rc->color = RB_BLACK;
                updateHeight(b->rc);
            }
            b->color = RB_BLACK;
        }else{       // 黑孩子无红色节点
            s->color = RB_RED;
            s->height --;
            if(IsRed(p)){              // BB-2R
                p->color = RB_BLACK;
            }else{                      // BB-2B
                p->height --;
                updateHeight(p);
            }
        }
    }else{         // BB-3
        s->color = RB_BLACK;
        p->color = RB_RED;
        BinNodePosi(T) t = IsLChild(*s)?s->lc:s->rc;
        this->_hot = p;
        FromParentTo(*p) =this->rotateAt(t);
        solveDoubleBlack(r);
    }
}

template <typename T>
bool RBTree<T>::remove(const T&e){            // 删除
    BinNodePosi(T) x = this->search(e);
    if(!x) return false;                      // 确保目标存在

    BinNodePosi(T) r = this->removeAt(x,this->_hot);    // 实际删除，返回被删除节点的succ
    if(!(--this->_size)) return true;
    // 如果刚被删除的根节点 则将其置黑，并更新黑高度
    if(! this->_hot){
        if(this->_root){
            this->_root->color = RB_BLACK;
            updateHeight(this->_root);

        }
        return true;
    }

    if(BlackHeightUpdated(*(this->_hot)))   return true;         // 如果依然平衡
    /**
     * 接下来的阶段说明被删除的节点并不平衡
     * 被删除的节点是黑色的，被删除后黑高度 - 1
     *
     * 如果succ是红色的，那么将其染色为黑色， 则黑高度就保持不变
     * 如果succ是黑色的，那么将无法其再染色为黑色， 则黑高度-1， 需要进行双黑缺陷的修正
     */

    if(IsRed(r)){
        r->color = RB_BLACK;
        r->height ++;
        return true;
    }
    solveDoubleBlack(r);
    return true;



}

template <typename T>
BinNodePosi(T) RBTree<T>::insert(const T& e){    // 插入
    BinNodePosi(T) x = this->search(e);
    if(x) return x;                                // 如果找到了e， 直接返回
    if(this->_hot == NULL){
        x = new BinNode<T>(e,this->_hot, NULL, NULL, -1);
        this->_root = x;

    }else{
        if(e < this->_hot->data){
            x = new BinNode<T>(e,this->_hot, NULL, NULL, -1);
            this->_hot->lc = x;
        }else{
            x = new BinNode<T>(e,this->_hot, NULL, NULL, -1);
            this->_hot->rc = x;
        }
    }

    this->_size ++;
    solveDoubleRed(x);
    return x ? x : this->_hot->parent;
}
template <typename T>
void RBTree<T>::solveDoubleRed(BinNodePosi(T) x){
    // 如果递归到树根，则将其转黑, 整个树的黑高度也随之递增
    if (IsRoot(*x)){
        this->_root->color = RB_BLACK;
        this->_root->height ++;
        return;
    }

    BinNodePosi(T) p = x->parent; if(IsBlack(p)) return;          // 父节点为黑色
    BinNodePosi(T) g = p->parent;
    BinNodePosi(T) u = uncle(x);                                  // 叔叔

    if(IsBlack(u)){                                               // 叔父为黑色
        if(IsLChild(*x) == IsLChild(*p)){
            p->color = RB_RED;
        }else{
            x->color = RB_BLACK;
        }

        // 对其 进行旋转
        BinNodePosi(T) gg = g->parent;
        BinNodePosi(T) r = FromParentTo(*g) = this->rotateAt(x);    //
        r->parent = gg;
    }else{
        p->color = RB_BLACK;   p->height ++;
        u->color = RB_BLACK;   u->height ++;
        if(!IsRoot(*g))  g->color = RB_RED;
        solveDoubleRed(g);           // 继续调整
    }

}
/**
 * 以p进行右旋
 *                 g
 *        p
 *    v
 *
 *
 *               g
 *        v
 *             p
 */
template <typename T>
void RBTree<T>::rightRotate(BinNodePosi(T) p){
    BinNodePosi(T) g = p->parent;
    BinNodePosi(T) v = p->lc;
    BinNodePosi(T) vrc = v->rc;
    BinNodePosi(T)& fromParentReference = FromParentTo(*p);

    v->parent = g;
    fromParentReference = v;

    v->rc = p;
    p->parent = v;

    p->lc = vrc;
    if(vrc) vrc->parent = p;

}


/**
 * 以p进行左旋
 *   g
 *        p
 *              v
 *
 *
 *     g
 *            v
 *        p
 */

template <typename T>
void RBTree<T>::leftRotate(BinNodePosi(T) p){

    BinNodePosi(T) g = p->parent;
    BinNodePosi(T) v = p->rc;
    BinNodePosi(T) vlc = v->lc;
    BinNodePosi(T)& fromParentReference = FromParentTo(*p);

    v->parent = g;
    fromParentReference = v;

    v->lc = p;
    p->parent = v;

    p->rc = vlc;
    if(vlc) vlc->parent = p;

}

#endif //CPP_LEARNING_RB_TREE_H
